// https://juejin.cn/post/6844903814340804615

// 冒泡排序
// 大致流程：
// 从第一个元素开始，比较每两个相邻元素，如果前者大，就交换位置
// 每次遍历结束，能够找到该次遍历过的元素中的最大值
// 如果还有没排序过的元素，继续1
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length -1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr, j ,j+1)
      }
    }
  }
  return arr
}
// 后面还会多次用到，就不再写出来了
function swap(arr, n, m) {
  [arr[n], arr[m]] = [arr[m], arr[n]]
}

let sortArr = bubbleSort([10, 3, 19, 30, 20])
console.log("sortArr=====>", sortArr);

// 优化1
// 检查某次内层遍历是否发生交换。
// 如果没有发生交换，说明已经排序完成，就算外层循环还没有执行完 length-1 次也可以直接 break。

function bubbleSort1(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 外层循环初始值为 false，没有发生交换
    let has_exchanged = false
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j ,j+1)
        has_exchanged = true
      }
    }
    // 内层循环结束判断一下是否发生了交换
    if (!has_exchanged) break
  }
  return arr
}

// 优化2   ,  后面都已经拍好序了
// 记录内层遍历最后一次发生交换的位置，下一次外层遍历只需要到这个位置就可以了。
// 那么外层遍历就不能用 for 了，因为每次遍历的结束位置可能会发生改变。
function bubbleSort2(arr) {
  // 遍历结束位置的初始值为数组尾，并逐渐向数组头部逼近
  let high = arr.length - 1
  while (high > 0) {
    // 本次内层遍历发生交换的位置的初始值
    let position = 0
    for (let j = 0; j < high; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        // 如果发生了交换，更新 position
        position = j
      }
    }
    // 下次遍历只需要到 position 的位置即可
    high = position
  }
  return arr
}

// 选择排序 ================================================================>
// 大致流程：
// 取出未排序部分的第一个元素，遍历该元素之后的部分并比较大小。对于第一次遍历，就是取出第一个元素
// 如果有更小的，与该元素交换位置
// 每次遍历都能找出剩余元素中的最小值并放在已排序部分的最后

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min_index = i
    // 遍历后面的部分，寻找更小值
    for (let j = i + 1; j < arr.length; j++) {
      // 如果有，更新min_index
      if (arr[j] < arr[min_index]) min_index = j
    }
    swap(arr, i, min_index)
  }
  return arr
}


//插入排序 ====================================================>
// 大致流程：

// 取未排序部分的第一个元素。第一次遍历时，将第一个元素作为已排序元素，从第二个元素开始取
// 遍历前面的已排序元素，并与这个未排序元素比较大小，找到合适的位置插入
// 继续执行1
// 和选择排序好像有一点类似的地方：
// 选择排序，先找合适的元素，然后直接放到已排序部分
// 插入排序，先按顺序取元素，再去已排序部分里找合适的位置
// 第二种理解方式：
// 在前面的第2步中，相当于把已排序部分末尾添加一个元素，并且执行一次冒泡排序。  因为前面的数组是已排序的，所以冒泡只需要遍历一次就可以给新的元素找到正确的位置。
// 但是以这种方式实现的代码无法使用二分法进行优化。
// 那么是不是说明，冒泡排序的优化方法可以用在这里？
// 并不是。因为冒泡排序主要从两方面进行优化：
// 减少外层遍历次数
// 增加每次遍历找到的极值个数

// 按照第一种理解方式的实现，即一般的实现
function insertionSort(arr) {
  for (let index = 1; index < arr.length; index++) {
    // 取出一个未排序元素
    let current_ele = arr[index]
    // 已排序元素的最后一个的位置
    let ordered_index = index - 1
    // 前面的元素更大，并且还没遍历完
    while (arr[ordered_index] >= current_ele && ordered_index >= 0) {
      // 使用前面的值覆盖当前的值
      arr[ordered_index + 1] = arr[ordered_index]
      // 向前移动一个位置
      ordered_index--
    }
    // 遍历完成，前面的元素都比当前元素小，把未排序元素赋值进去
    arr[ordered_index + 1] = current_ele
  }
  return arr
}
// 按照第二种理解方式的实现
function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 对前面的已排序数组和新选出来的元素执行一趟冒泡排序
    for (let j = i + 1; j >= 0; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1)
      }
    } 
  }
  return arr
}

/**
 * @func 快速排序
 * @desc
 * 1.定义快排的数组参数
 * 2.检查数组中的长度，如果小于等于1则直接返回
 * 3.选择枢轴，将其与原始数组分开，并定义两个空数组来存储两个子集
 * 4.遍历数组，小于主元的元素放入左子集中，大于主元的元素放入右子集中
 * @param {
 *  arr: Array<number>
 * }
 * @return {
 *  arr: Array<number>
 * }
 */

let arr = [86, 24, 64, 48, 15, 30, 90, 49]

const quickSort = (arr) => {
    // 检查数组中的长度，如果小于等于1则直接返回
    if (arr.length <= 1) {
        return arr
    }
    // 选择枢轴，将其与原始数组分开，并定义两个空数组来存储两个子集
    let pivotIndex = Math.floor(arr.length / 2)
    let pivot = arr.splice(pivotIndex, 1)[0] // 这个操作会删除中间枢纽
    let left = []
    let right = []
    // 遍历数组，小于主元的元素放入左子集中，大于主元的元素放入右子集中
    for (let index = 0; index < arr.length; index++) {
        const ele = arr[index];
        if (ele < pivot) {
            left.push(ele)
        } else {
            right.push(ele)
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}

const sortArr1 = quickSort(arr)
console.log("sortArr", sortArr1);